# -*- coding: utf-8 -*-
from __future__ import print_function

import sys
import os
import copy

reload(sys)
sys.setdefaultencoding("utf-8")


def combinationSum(candidates, target):
    """
    :type candidates: List[int]
    :type target: int
    :rtype: List[List[int]]
    """
    candidates.sort()
    n = len(candidates)
    res = []

    def backtrack(i, tmp_sum, tmp):
        for j in range(i, n):
            # 如果和超过了target值，停止遍历，返回上层函数
            if tmp_sum + candidates[j] > target:
                break
            # 如果和等于target值，把结果添加进去，后面也没必要继续遍历了，停止遍历，返回上层函数
            if tmp_sum + candidates[j] == target:
                res.append(tmp + [candidates[j]])
                break
            backtrack(j, tmp_sum + candidates[j], tmp + [candidates[j]])

    backtrack(0, 0, [])
    return res


combinationSum([2,3,6,7], 7)

